Celestin Apprentice 7/Apprentice-Release7.iso/Environments/PowerLisp 2.01/Supplemental Documentation/Documentation/Chapter 17. Arrays

Text File | 1995-03-27 | 39KB | 879 lines

Common Lisp the Language, 2nd Edition
-------------------------------------------------------------------------------

17. Arrays

An array is an object with components arranged according to a rectilinear
coordinate system. In principle, an array in Common Lisp may have any number of
dimensions, including zero. (A zero-dimensional array has exactly one element.)
In practice, an implementation may limit the number of dimensions supported,
but every Common Lisp implementation must support arrays of up to seven
dimensions. Each dimension is a non-negative integer; if any dimension of an
array is zero, the array has no elements.

An array may be a general array, meaning each element may be any Lisp object,
or it may be a specialized array, meaning that each element must be of a given
restricted type.

[old_change_begin]
One-dimensional arrays are called vectors. General vectors may contain any Lisp
object. Vectors whose elements are restricted to type string-char are called
strings. Vectors whose elements are restricted to type bit are called
bit-vectors.
[old_change_end]

[change_begin]
X3J13 voted in March 1989 (CHARACTER-PROPOSAL)   to eliminate the type
string-char and to redefine the type string to be the union of one or more
specialized vector types, the types of whose elements are subtypes of the type
character.
[change_end]

-------------------------------------------------------------------------------

   *  Array Creation
   *  Array Access
   *  Array Information
   *  Functions on Arrays of Bits
   *  Fill Pointers
   *  Changing the Dimensions of an Array

-------------------------------------------------------------------------------

17.1. Array Creation

Do not be daunted by the many options of the function make-array. All that is
required to construct an array is a list of the dimensions; most of the options
are for relatively esoteric applications.

[Function]
make-array dimensions &key :element-type :initial-element :initial-contents
:adjustable :fill-pointer :displaced-to :displaced-index-offset

This is the primitive function for making arrays. The dimensions argument
should be a list of non-negative integers that are to be the dimensions of the
array; the length of the list will be the dimensionality of the array. Each
dimension must be smaller than array-dimension-limit, and the product of all
the dimensions must be smaller than array-total-size-limit. Note that if
dimensions is nil, then a zero-dimensional array is created. For convenience
when making a one-dimensional array, the single dimension may be provided as an
integer rather than as a list of one integer.

An implementation of Common Lisp may impose a limit on the rank of an array,
but this limit may not be smaller than 7. Therefore, any Common Lisp program
may assume the use of arrays of rank 7 or less. The implementation-dependent
limit on array rank is reflected in array-rank-limit.

The keyword arguments for make-array are as follows:

:element-type
     This argument should be the name of the type of the elements of the array;
     an array is constructed of the most specialized type that can nevertheless
     accommodate elements of the given type. The type t specifies a general
     array, one whose elements may be any Lisp object; this is the default
     type.

[change_begin]

     X3J13 voted in January 1989 (ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS)   to
     change typep and subtypep so that the specialized array type specifier
     means the same thing for discrimination purposes as for declaration
     purposes: it encompasses those arrays that can result by specifying
     element-type as the element type to the function make-array. Therefore we
     may say that if type is the :element-type argument, then the result will
     be an array of type (array type); put another way, for any type A,

     (typep (make-array ... :element-type 'A ...)
            '(array A)))

     is always true. See upgraded-array-element-type.

[change_end]

:initial-element
     This argument may be used to initialize each element of the array. The
     value must be of the type specified by the :element-type argument. If the
     :initial-element option is omitted, the initial values of the array
     elements are undefined (unless the :initial-contents or :displaced-to
     option is used). The :initial-element option may not be used with the
     :initial-contents or :displaced-to option.

:initial-contents
     This argument may be used to initialize the contents of the array. The
     value is a nested structure of sequences. If the array is
     zero-dimensional, then the value specifies the single element. Otherwise,
     the value must be a sequence whose length is equal to the first dimension;
     each element must be a nested structure for an array whose dimensions are
     the remaining dimensions, and so on. For example:

     (make-array '(4 2 3)
                 :initial-contents
                 '(((a b c) (1 2 3))
                   ((d e f) (3 1 2))
                   ((g h i) (2 3 1))
                   ((j k l) (0 0 0))))

     The numbers of levels in the structure must equal the rank of the array.
     Each leaf of the nested structure must be of the type specified by the
     :type option. If the :initial-contents option is omitted, the initial
     values of the array elements are undefined (unless the :initial-element or
     :displaced-to option is used). The :initial-contents option may not be
     used with the :initial-element or :displaced-to option.

:adjustable
     This argument, if specified and not nil, indicates that it must be
     possible to alter the array's size dynamically after it is created. This
     argument defaults to nil.

[change_begin]

     X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that
     if this argument is non-nil then the predicate adjustable-array-p will
     necessarily be true when applied to the resulting array; but if this
     argument is nil (or omitted) then the resulting array may or may not be
     adjustable, depending on the implementation, and therefore
     adjustable-array-p may be correspondingly true or false of the resulting
     array. Common Lisp provides no portable way to create a non-adjustable
     array, that is, an array for which adjustable-array-p is guaranteed to be
     false.

[change_end]

:fill-pointer
     This argument specifies that the array should have a fill pointer. If this
     option is specified and not nil, the array must be one-dimensional. The
     value is used to initialize the fill pointer for the array. If the value t
     is specified, the length of the array is used; otherwise the value must be
     an integer between 0 (inclusive) and the length of the array (inclusive).
     This argument defaults to nil.

:displaced-to
     This argument, if specified and not nil, specifies that the array will be
     a displaced array. The argument must then be an array; make-array will
     create an indirect or shared array that shares its contents with the
     specified array. In this case the :displaced-index-offset option may be
     useful. It is an error if the array given as the :displaced-to argument
     does not have the same :element-type as the array being created. The
     :displaced-to option may not be used with the :initial-element or
     :initial-contents option. This argument defaults to nil.

:displaced-index-offset
     This argument may be used only in conjunction with the displaced-to
     option. It must be a non-negative integer (it defaults to zero); it is
     made to be the index-offset of the created shared array.

     When an array A is given as the :displaced-to argument to make-array when
     creating array B, then array B is said to be displaced to array A. Now the
     total number of elements in an array, called the total size of the array,
     is calculated as the product of all the dimensions (see array-total-size).
     It is required that the total size of A be no smaller than the sum of the
     total size of B plus the offset n specified by the :displaced-index-offset
     argument. The effect of displacing is that array B does not have any
     elements of its own but instead maps accesses to itself into accesses to
     array A. The mapping treats both arrays as if they were one-dimensional by
     taking the elements in row-major order, and then maps an access to element
     k of array B to an access to element k+n of array A.

If make-array is called with each of the :adjustable, :fill-pointer, and
:displaced-to arguments either unspecified or nil, then the resulting array is
guaranteed to be a simple array (see section 2.5).

[change_begin]
X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that if one
or more of the :adjustable, :fill-pointer, and :displaced-to arguments is true,
then whether the resulting array is simple is unspecified.
[change_end]

Here are some examples of the use of make-array:

;;; Create a one-dimensional array of five elements.
(make-array 5)

;;; Create a two-dimensional array, 3 by 4, with four-bit elements.
(make-array '(3 4) :element-type '(mod 16))

;;; Create an array of single-floats.
(make-array 5 :element-type 'single-float))

;;; Making a shared array.
(setq a (make-array '(4 3)))
(setq b (make-array 8 :displaced-to a
                      :displaced-index-offset 2))
;;; Now it is the case that:
        (aref b 0) == (aref a 0 2)
        (aref b 1) == (aref a 1 0)
        (aref b 2) == (aref a 1 1)
        (aref b 3) == (aref a 1 2)
        (aref b 4) == (aref a 2 0)
        (aref b 5) == (aref a 2 1)
        (aref b 6) == (aref a 2 2)
        (aref b 7) == (aref a 3 0)

The last example depends on the fact that arrays are, in effect, stored in
row-major order for purposes of sharing. Put another way, the indices for the
elements of an array are ordered lexicographically.

-------------------------------------------------------------------------------
Compatibility note: Both Lisp Machine Lisp, as described in reference [55], and
Fortran [15,3] store arrays in column-major order.
-------------------------------------------------------------------------------

[Constant]
array-rank-limit

The value of array-rank-limit is a positive integer that is the upper exclusive
bound on the rank of an array. This bound depends on the implementation but
will not be smaller than 8; therefore every Common Lisp implementation supports
arrays whose rank is between 0 and 7 (inclusive). (Implementors are encouraged
to make this limit as large as practicable without sacrificing performance.)

[Constant]
array-dimension-limit

The value of array-dimension-limit is a positive integer that is the upper
exclusive bound on each individual dimension of an array. This bound depends on
the implementation but will not be smaller than 1024. (Implementors are
encouraged to make this limit as large as practicable without sacrificing
performance.)

[change_begin]
X3J13 voted in January 1989 (FIXNUM-NON-PORTABLE)   to specify that the value
of array-dimension-limit must be of type fixnum. This in turn implies that all
valid array indices will be fixnums.
[change_end]

[Constant]
array-total-size-limit

The value of array-total-size-limit is a positive integer that is the upper
exclusive bound on the total number of elements in an array. This bound depends
on the implementation but will not be smaller than 1024. (Implementors are
encouraged to make this limit as large as practicable without sacrificing
performance.)

The actual limit on array size imposed by the implementation may vary according
to the :element-type of the array; in this case the value of
array-total-size-limit will be the smallest of these individual limits.

[Function]
vector &rest objects

The function vector is a convenient means for creating a simple general vector
with specified initial contents. It is analogous to the function list.

(vector       ...   )
   == (make-array (list n) :element-type t
             :initial-contents (list       ...   ))

-------------------------------------------------------------------------------

17.2. Array Access

The function aref is normally used for accessing an element of an array. Other
access functions, such as svref, char, and bit, may be more efficient in
specialized circumstances.

[Function]
aref array &rest subscripts

This accesses and returns the element of array specified by the subscripts. The
number of subscripts must equal the rank of the array, and each subscript must
be a non-negative integer less than the corresponding array dimension.

aref is unusual among the functions that operate on arrays in that it
completely ignores fill pointers. aref can access without error any array
element, whether active or not. The generic sequence function elt, however,
observes the fill pointer; accessing an element beyond the fill pointer with
elt is an error.

[change_begin]
Note that this remark, predating the design of the Common Lisp Object System,
uses the term ``generic'' in a generic sense and not necessarily in the
technical sense used by CLOS (see chapter 2).
[change_end]

setf may be used with aref to destructively replace an array element with a new
value.

Under some circumstances it is desirable to write code that will extract an
element from an array a given a list z of the indices, in such a way that the
code works regardless of the rank of the array. This is easy using apply:

(apply #'aref a z)

(The length of the list must of course equal the rank of the array.) This
construction may be used with setf to alter the element so selected to some new
value w:

(setf (apply #'aref a z) w)

[Function]
svref simple-vector index

The first argument must be a simple general vector, that is, an object of type
simple-vector. The element of the simple-vector specified by the integer index
is returned.

The index must be non-negative and less than the length of the vector.

setf may be used with svref to destructively replace a simple-vector element
with a new value.

svref is identical to aref except that it requires its first argument to be a
simple vector. In some implementations of Common Lisp, svref may be faster than
aref in situations where it is applicable. See also schar and sbit.

-------------------------------------------------------------------------------

17.3. Array Information

The following functions extract from an array interesting information other
than the elements.

[Function]
array-element-type array

array-element-type returns a type specifier for the set of objects that can be
stored in the array. This set may be larger than the set requested when the
array was created; for example, the result of

(array-element-type (make-array 5 :element-type '(mod 5)))

could be (mod 5), (mod 8), fixnum, t, or any other type of which (mod 5) is a
subtype. See subtypep.

[Function]
array-rank array

This returns the number of dimensions (axes) of array. This will be a
non-negative integer. See array-rank-limit.

-------------------------------------------------------------------------------
Compatibility note: In Lisp Machine Lisp, this is called array-#-dims. This
name causes problems in other Lisp dialects because of the # character.
-------------------------------------------------------------------------------

[Function]
array-dimension array axis-number

The length of dimension number axis-number of the array is returned. array may
be any kind of array, and axis-number should be a non-negative integer less
than the rank of array. If the array is a vector with a fill pointer,
array-dimension returns the total size of the vector, including inactive
elements, not the size indicated by the fill pointer. (The function length will
return the size indicated by the fill pointer.)

-------------------------------------------------------------------------------
Compatibility note: This is similar to the Lisp Machine Lisp function
array-dimension-n, but takes its arguments in the other order, and is
zero-origin for consistency instead of one-origin. In Lisp Machine Lisp
(array-dimension-n 0) returns the length of the array leader.
-------------------------------------------------------------------------------

[Function]
array-dimensions array

array-dimensions returns a list whose elements are the dimensions of array.

[Function]
array-total-size array

array-total-size returns the total number of elements in the array, calculated
as the product of all the dimensions.

(array-total-size x)
   == (apply #'* (array-dimensions x))
   == (reduce #'* (array-dimensions x))

Note that the total size of a zero-dimensional array is 1. The total size of a
one-dimensional array is calculated without regard for any fill pointer.

[Function]
array-in-bounds-p array &rest subscripts

This predicate checks whether the subscripts are all legal subscripts for
array. The predicate is true if they are all legal; otherwise it is false. The
subscripts must be integers. The number of subscripts supplied must equal the
rank of the array. Like aref, array-in-bounds-p ignores fill pointers.

[Function]
array-row-major-index array &rest subscripts

This function takes an array and valid subscripts for the array and returns a
single non-negative integer less than the total size of the array that
identifies the accessed element in the row-major ordering of the elements. The
number of subscripts supplied must equal the rank of the array. Each subscript
must be a non-negative integer less than the corresponding array dimension.
Like aref, array-row-major-index ignores fill pointers.

A possible definition of array-row-major-index, with no error checking, would
be

(defun array-row-major-index (a &rest subscripts)
  (apply #'+ (maplist #'(lambda (x y)
                          (* (car x) (apply #'* (cdr y))))
                      subscripts
                      (array-dimensions a))))

For a one-dimensional array, the result of array-row-major-index always equals
the supplied subscript.

[change_begin]

[Function]
row-major-aref array index

X3J13 voted in March 1988 (AREF-1D)   to add the function row-major-aref. This
allows any array element to be accessed as if the containing array were
one-dimensional. The index must be a non-negative integer less than the total
size of the array. It indexes into the array as if its elements were arranged
one-dimensionally in row-major order. It may be understood in terms of aref as
follows:

(row-major-aref array index) ==
  (aref (make-array (array-total-size array))
                    :displaced-to array
                    :element-type (array-element-type array))
        index)

In other words, one may treat an array as one-dimensional by creating a new
one-dimensional array that is displaced to the old one and then accessing the
new array. Alternatively, aref may be understood in terms of row-major-aref:

(aref array       ...   ) ==
  (row-major-aref array
                  (array-row-major-index array       ...   )

That is, a multidimensional array access is equivalent to a row-major access
using an equivalent row-major index.

Like aref, row-major-aref completely ignores fill pointers. A call to
row-major-setf is suitable for use as a place for setf.

This operation makes it easier to write code that efficiently processes arrays
of any rank. Suppose, for example, that one wishes to set every element of an
array tennis-scores to zero. One might write

(fill (make-array (array-total-size tennis-scores)
                  :element-type (array-element-type tennis-scores)
                  :displaced-to tennis-scores)
      0)

Unfortunately, this incurs the overhead of creating a displaced array, and fill
cannot be applied to multidimensional arrays. Another approach would be to
handle each possible rank separately:

(ecase (array-rank tennis-scores)
  (0 (setf (aref tennis-scores) 0))
  (1 (dotimes (i0 (array-dimension tennis-scores 0))
       (setf (aref tennis-scores i0) 0)))
  (2 (dotimes (i0 (array-dimension tennis-scores 0))
       (dotimes (i1 (array-dimension tennis-scores 1))
         (setf (aref tennis-scores i0 i1) 0))))
  ...
  (7 (dotimes (i0 (array-dimension tennis-scores 0))
       (dotimes (i1 (array-dimension tennis-scores 1))
         (dotimes (i2 (array-dimension tennis-scores 1))
           (dotimes (i3 (array-dimension tennis-scores 1))
             (dotimes (i4 (array-dimension tennis-scores 1))
               (dotimes (i5 (array-dimension tennis-scores 1))
                 (dotimes (i6 (array-dimension tennis-scores 1))
                   (setf (aref tennis-scores i0 i1 i2 i3 i4 i5 i6)
                         0)))))))))
  )

It is easy to get tired of writing such code. Furthermore, this approach is
undesirable because some implementations of Common Lisp will in fact correctly
support arrays of rank greater than 7 (though no implementation is required to
do so). A recursively nested loop does the job, but it is still pretty hairy:

(labels
  ((grok-any-rank (&rest indices)
     (let ((d (- (array-rank tennis-scores) (length indices)))
       (if (= d 0)
           (setf (apply #'row-major-aref indices) 0)
           (dotimes (i (array-dimension tennis-scores (- d 1)))
             (apply #'grok-any-rank i indices))))))
  (grok-any-rank))

Whether this code is particularly efficient depends on many implementation
parameters, such as how &rest arguments are handled and how cleverly calls to
apply are compiled. How much easier it is to use row-major-aref!

(dotimes (i (array-total-size tennis-scores))
  (setf (row-major-aref tennis-scores i) 0))

Surely this code is sweeter than the honeycomb.
[change_end]

[Function]
adjustable-array-p array

This predicate is true if the argument (which must be an array) is adjustable,
and otherwise is false.

[change_begin]
X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that
adjustable-array-p is true of an array if and only if adjust-array, when
applied to that array, will return the same array, that is, an array eq to the
original array. If the :adjustable argument to make-array is non-nil when an
array is created, then adjustable-array-p must be true of that array. If an
array is created with the :adjustable argument nil (or omitted), then
adjustable-array-p may be true or false of that array, depending on the
implementation. X3J13 further voted to define the terminology ``adjustable
array'' to mean precisely ``an array of which adjustable-array-p is true.'' See
make-array and adjust-array.
[change_end]

-------------------------------------------------------------------------------

17.4. Functions on Arrays of Bits

The functions described in this section operate only on arrays of bits, that
is, specialized arrays whose elements are all 0 or 1.

[Function]
bit bit-array &rest subscripts
sbit simple-bit-array &rest subscripts

bit is exactly like aref but requires an array of bits, that is, one of type
(array bit). The result will always be 0 or 1. sbit is like bit but
additionally requires that the first argument be a simple array (see section
2.5). Note that bit and sbit, unlike char and schar, allow the first argument
to be an array of any rank.

setf may be used with bit or sbit to destructively replace a bit-array element
with a new value.

bit and sbit are identical to aref except for the more specific type
requirements on the first argument. In some implementations of Common Lisp, bit
may be faster than aref in situations where it is applicable, and sbit may
similarly be faster than bit.

[Function]

bit-and bit-array1 bit-array2 &optional result-bit-array
bit-ior bit-array1 bit-array2 &optional result-bit-array
bit-xor bit-array1 bit-array2 &optional result-bit-array
bit-eqv bit-array1 bit-array2 &optional result-bit-array
bit-nand bit-array1 bit-array2 &optional result-bit-array
bit-nor bit-array1 bit-array2 &optional result-bit-array
bit-andc1 bit-array1 bit-array2 &optional result-bit-array
bit-andc2 bit-array1 bit-array2 &optional result-bit-array
bit-orc1 bit-array1 bit-array2 &optional result-bit-array
bit-orc2 bit-array1  bit-array2 &optional result-bit-array

These functions perform bit-wise logical operations on bit-arrays. All of the
arguments to any of these functions must be bit-arrays of the same rank and
dimensions. The result is a bit-array of matching rank and dimensions, such
that any given bit of the result is produced by operating on corresponding bits
from each of the arguments.

If the third argument is nil or omitted, a new array is created to contain the
result. If the third argument is a bit-array, the result is destructively
placed into that array. If the third argument is t, then the first argument is
also used as the third argument; that is, the result is placed back in the
first array.

The following table indicates what the result bit is for each operation as a
function of the two corresponding argument bits.

argument1  0  0  1  1
argument2  0  1  0  1  Operation name
------------------------------------------------------------
bit-and    0  0  0  1  and
bit-ior    0  1  1  1  inclusive or
bit-xor    0  1  1  0  exclusive or
bit-eqv    1  0  0  1  equivalence (exclusive nor)
bit-nand   1  1  1  0  not-and
bit-nor    1  0  0  0  not-or
bit-andc1  0  1  0  0  and complement of argument1 with argument2
bit-andc2  0  0  1  0  and argument1 with complement of argument2
bit-orc1   1  1  0  1  or complement of argument1 with argument2
bit-orc2   1  0  1  1  or argument1 with complement of argument2
------------------------------------------------------------

For example:

(bit-and #*1100 #*1010) => #*1000
(bit-xor #*1100 #*1010) => #*0110
(bit-andc1 #*1100 #*1010) => #*0100

See logand and related functions.

[Function]
bit-not bit-array &optional result-bit-array

The first argument must be an array of bits. A bit-array of matching rank and
dimensions is returned that contains a copy of the argument with all the bits
inverted. See lognot.

If the second argument is nil or omitted, a new array is created to contain the
result. If the second argument is a bit-array, the result is destructively
placed into that array. If the second argument is t, then the first argument is
also used as the second argument; that is, the result is placed back in the
first array.

-------------------------------------------------------------------------------

17.5. Fill Pointers

Several functions for manipulating a fill pointer are provided in Common Lisp
to make it easy to incrementally fill in the contents of a vector and, more
generally, to allow efficient varying of the length of a vector. For example, a
string with a fill pointer has most of the characteristics of a PL/I varying
string.

The fill pointer is a non-negative integer no larger than the total number of
elements in the vector (as returned by array-dimension); it is the number of
``active'' or ``filled-in'' elements in the vector. The fill pointer
constitutes the ``active length'' of the vector; all vector elements whose
index is less than the fill pointer are active, and the others are inactive.
Nearly all functions that operate on the contents of a vector will operate only
on the active elements. An important exception is aref, which can be used to
access any vector element whether in the active region of the vector or not. It
is important to note that vector elements not in the active region are still
considered part of the vector.

-------------------------------------------------------------------------------
Implementation note: An implication of this rule is that vector elements
outside the active region may not be garbage-collected.
-------------------------------------------------------------------------------

Only vectors (one-dimensional arrays) may have fill pointers; multidimensional
arrays may not. (Note, however, that one can create a multidimensional array
that is displaced to a vector that has a fill pointer.)

[Function]
array-has-fill-pointer-p array

The argument must be an array. array-has-fill-pointer-p returns t if the array
has a fill pointer, and otherwise returns nil. Note that
array-has-fill-pointer-p always returns nil if the array is not
one-dimensional.

[Function]
fill-pointer vector

The fill pointer of vector is returned. It is an error if the vector does not
have a fill pointer.

setf may be used with fill-pointer to change the fill pointer of a vector. The
fill pointer of a vector must always be an integer between zero and the size of
the vector (inclusive).

[Function]
vector-push new-element vector

vector must be a one-dimensional array that has a fill pointer, and new-element
may be any object. vector-push attempts to store new-element in the element of
the vector designated by the fill pointer, and to increase the fill pointer by
1. If the fill pointer does not designate an element of the vector
(specifically, when it gets too big), it is unaffected and vector-push returns
nil. Otherwise, the store and increment take place and vector-push returns the
former value of the fill pointer (1 less than the one it leaves in the vector);
thus the value of vector-push is the index of the new element pushed.

[change_begin]
It is instructive to compare vector-push, which is a function, with push, which
is a macro that requires a place suitable for setf. A vector with a fill
pointer effectively contains the place to be modified in its fill-pointer slot.

[change_end]

[Function]
vector-push-extend new-element vector &optional extension

vector-push-extend is just like vector-push except that if the fill pointer
gets too large, the vector is extended (using adjust-array) so that it can
contain more elements. If, however, the vector is not adjustable, then
vector-push-extend signals an error.

[change_begin]
X3J13 voted in June 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to clarify that
vector-push-extend regards an array as not adjustable if and only if
adjustable-array-p is false of that array.
[change_end]

The optional argument extension, which must be a positive integer, is the
minimum number of elements to be added to the vector if it must be extended; it
defaults to a ``reasonable'' implementation-dependent value.

[Function]
vector-pop vector

vector must be a one-dimensional array that has a fill pointer. If the fill
pointer is zero, vector-pop signals an error. Otherwise the fill pointer is
decreased by 1, and the vector element designated by the new value of the fill
pointer is returned.

-------------------------------------------------------------------------------

17.6. Changing the Dimensions of an Array

This function may be used to resize or reshape an array. Its options are
similar to those of make-array.

[Function]
adjust-array array new-dimensions &key :element-type :initial-element
:initial-contents :fill-pointer :displaced-to :displaced-index-offset

adjust-array takes an array and a number of other arguments as for make-array.
The number of dimensions specified by new-dimensions must equal the rank of
array.

adjust-array returns an array of the same type and rank as array, with the
specified new-dimensions. In effect, the array argument itself is modified to
conform to the new specifications, but this may be achieved either by modifying
the array or by creating a new array and modifying the array argument to be
displaced to the new array.

In the simplest case, one specifies only the new-dimensions and possibly an
:initial-element argument. Those elements of array that are still in bounds
appear in the new array. The elements of the new array that are not in the
bounds of array are initialized to the :initial-element; if this argument is
not provided, then the initial contents of any new elements are undefined.

If :element-type is specified, then array must be such that it could have been
originally created with that type; otherwise an error is signaled. Specifying
:element-type to adjust-array serves only to require such an error check.

If :initial-contents or :displaced-to is specified, then it is treated as for
make-array. In this case none of the original contents of array appears in the
new array.

If :fill-pointer is specified, the fill pointer of the array is reset as
specified. An error is signaled if array had no fill pointer already.

[change_begin]
X3J13 voted in June 1988 (ADJUST-ARRAY-FILL-POINTER)   to clarify the treatment
of the :fill-pointer argument as follows.

If the :fill-pointer argument is not supplied, then the fill pointer of the
array is left alone. It is an error to try to adjust the array to a total size
that is smaller than its fill pointer.

If the :fill-pointer argument is supplied, then its value must be either an
integer, t, or nil. If it is an integer, then it is the new value for the fill
pointer; it must be non-negative and no greater than the new size to which the
array is being adjusted. If it is t, then the fill pointer is set equal to the
new size for the array. If it is nil, then the fill pointer is left alone; it
is as if the argument had not been supplied. Again, it is an error to try to
adjust the array to a total size that is smaller than its fill pointer.

An error is signaled if a non-nil :fill-pointer value is supplied and the array
to be adjusted does not already have a fill pointer.

This extended treatment of the :fill-pointer argument to adjust-array is
consistent with the previously existing treatment of the :fill-pointer argument
to make-array.
[change_end]

adjust-array may, depending on the implementation and the arguments, simply
alter the given array or create and return a new one. In the latter case the
given array will be altered so as to be displaced to the new array and have the
given new dimensions.

[old_change_begin]
It is not permitted to call adjust-array on an array that was not created with
the :adjustable option. The predicate adjustable-array-p may be used to
determine whether or not an array is adjustable.
[old_change_end]

[change_begin]
X3J13 voted in January 1989 (ADJUST-ARRAY-NOT-ADJUSTABLE)   to allow
adjust-array to be applied to any array. If adjust-array is applied to an array
that was originally created with :adjustable true, the array returned is eq to
its first argument. It is not specified whether adjust-array returns an array
eq to its first argument for any other arrays. If the array returned by
adjust-array is not eq to its first argument, the original array is unchanged
and does not share storage with the new array.

Under this new definition, it is wise to treat adjust-array in the same manner
as delete and nconc: one should carefully retain the returned value, for
example by writing

(setq my-array (adjust-array my-array ...))

rather than relying solely on a side effect.
[change_end]

If adjust-array is applied to an array that is displaced to another array x,
then afterwards neither array nor the returned result is displaced to x unless
such displacement is explicitly re-specified in the call to adjust-array.

For example, suppose that the 4-by-4 array m looks like this:

#2A( ( alpha     beta      gamma     delta )
     ( epsilon   zeta      eta       theta )
     ( iota      kappa     lambda    mu    )
     ( nu        xi        omicron   pi    ) )

Then the result of

(adjust-array m '(3 5) :initial-element 'baz)

is a 3-by-5 array with contents

#2A( ( alpha     beta      gamma     delta     baz )
     ( epsilon   zeta      eta       theta     baz )
     ( iota      kappa     lambda    mu        baz ) )

Note that if array a is created displaced to array b and subsequently array b
is given to adjust-array, array a will still be displaced to array b; the
effects of this displacement and the rule of row-major storage order must be
taken into account.

[change_begin]
X3J13 voted in June 1988 (ADJUST-ARRAY-DISPLACEMENT)   to clarify the
interaction of adjust-array with array displacement.

Suppose that an array A is to be adjusted. There are four cases according to
whether or not A was displaced before adjustment and whether or not the result
is displaced after adjustment.

   *  Suppose A is not displaced either before or after. The dimensions of A
     are altered, and the contents are rearranged as appropriate. Additional
     elements of A are taken from the :initial-element argument. However, the
     use of the :initial-contents argument causes all old contents to be
     discarded.

   *  Suppose A is not displaced before, but is displaced to array C after.
     None of the original contents of A appears in A afterwards; A now contains
     (some of) the contents of C, without any rearrangement of C.

   *  Suppose A is displaced to array B before the call, and is displaced to
     array C after the call. (Note that B and C may be the same array.) The
     contents of B do not appear in A afterwards (unless such contents also
     happen to be in C, as when B and C are the same, for example). If
     :displaced-index-offset is not specified in the call to adjust-array, it
     defaults to zero; the old offset (into B) is not retained.

   *  Suppose A is displaced to array B before the call, but is not displaced
     afterwards. In this case A gets a new ``data region'' and (some of) the
     contents of B are copied into it as appropriate to maintain the existing
     old contents. Additional elements of A are taken from the :initial-element
     argument. However, the use of the :initial-contents argument causes all
     old contents to be discarded.

If array X is displaced to array Y, and array Y is displaced to array Z, and
array Y is altered by adjust-array, array X must now refer to the adjusted
contents of Y. This means that an implementation may not collapse the chain to
make X refer to Z directly and forget that the chain of reference passes
through array Y. (Caching techniques are of course permitted, as long as they
preserve the semantics specified here.)

If X is displaced to Y, it is an error to adjust Y in such a way that it no
longer has enough elements to satisfy X. This error may be signaled at the time
of the adjustment, but this is not required.

Note that omitting the :displaced-to argument to adjust-array is equivalent to
specifying :displaced-to nil; in either case, the array is not displaced after
the call regardless of whether it was displaced before the call.
[change_end]

-------------------------------------------------------------------------------